1. Field of the Invention
The present invention relates to the field of multi-objective optimization methods, and especially to methods of solving large-scale design optimization task.
2. Background Art
Optimization methods started with Newton's method, which was described by Isaac Newton in “De Analysi Per Aequationes Numero Terminorum Infinitas,” written in 1669. Since then many methods for optimization of functions have been developed and applied for solving a variety of technical and scientific problems. Modern applied mathematics includes a large collection of optimization methods created over three centuries. An important group of such methods is based on using 1st and 2nd order derivatives of objective function [5,6,7] (Newton-Ralphson, Steepest descent, Conjugate gradient, Sequential quadratic programming, etc).
Italian economist Vilfredo Pareto introduced the concept of Pareto optimality in 1906 (see below multi-objective optimization problem formulation (1)-(2)). The concept has broad applications in economics and engineering. The Pareto optimality concept became the starting point for a new discipline of multi-objective optimization, which is intended to find trade-offs for several contradicting objectives. For instance, survivability and cost are contradicting objectives in ship design. If survivability is improved then cost may become too high. If the cost is decreased then survivability may become worse. It is important to find a reasonable trade-off for these two objectives, which determines the practical value of the multi-objective optimization concept.
The general multi-objective optimization problem is posed as follows [1]:Minimize: F(X)=[F1(X), F2(X), . . . , Fm(X)]T   (1)subject to: qj(X)≦0; j=1,2, . . . k   (2)
The feasible design space X (often called the feasible decision space or constraint set) is defined as the set {X|qj(X)≦0; j=1,2, . . . k}. Feasibility implies that no constraint is violated. Objective functions, also named criteria, Fi(X), i=1, . . . , m and constraints qj(X), j=1,2, . . . k are often called model output variables, or dependent variables.
The dimension of multi-objective optimization tasks can be very different from two-dimensional tasks like the task (A.1.1) to large-scale tasks with dozens of objective functions and thousands of independent variables typical for aerospace, automotive industries, ship design, etc. Today it is impossible to design an airplane, automobile, turbine, or ship without intensive use of multi-objective optimization algorithms. This determines market demand and practical value of efficient multi-objective optimization algorithms.
Attempts to solve such tasks were first based on using well developed gradient-based optimization methods. In order to use those single-objective methods for multi-objective optimization, a scalarization technique was developed, which allowed substitution of multiple objective functions by a weighted exponential sum of those functions. The following is the simplest and the most common form of scalarization for the optimization problem (1):
                              U          =                                    ∑                              i                =                1                            m                        ⁢                                                            w                  i                                ⁡                                  [                                                            F                      i                                        ⁡                                          (                      x                      )                                                        ]                                            p                                      ;                                            F              i                        ⁡                          (              x              )                                >          0                ;                  ∀          i                                    (        3        )            
In the early 1970's John Holland invented Genetic Algorithms (GAs). A genetic algorithm is a heuristic used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to optimization theory and other fields of computer science. Genetic algorithms use biologically derived techniques such as inheritance, mutation, natural selection, and crossover. GAs differs from conventional optimization algorithms in several fundamental respects. They do not use derivative or gradient information, but instead rely on the observed performance of evaluated solutions, and the transition rules are probabilistic rather than deterministic.
Thus, there are two groups of known multi-objective optimization methods: scalarization methods and multi-objective genetic algorithms.
1. Scalarization methods use a global criterion to combine multiple objective functions mathematically. These methods require solving a sequence of single-objective problems. The most common method of the group is the weighted sum method.
Use of gradients for determination of direction for the next step works perfectly when a single objective function is optimized. But utilizing the same technique for a weighted sum of multiple objective functions, does not allow controlling values of individual objective functions during the optimization process. It creates serious problems finding evenly distributed Pareto optimal points:
a. The existing weighted sum approaches widely used for design optimization do not work well with the non-convex Pareto surfaces [1], which have been shown to frequently occur in structural optimization and robust design.
b. Uniform distribution of Pareto optimal points cannot be guaranteed even if the weights are varying consistently and continuously. It means that Pareto set will be incomplete and inaccurate [2], which is also follows from FIGS. 1B-1C. This leads to the situation when the best optimal design solution is missed.
Using traditional gradient-based optimization algorithms are computationally expensive. Algorithms SQP and MMFD spend 93-97% of model evaluations for approaching the Pareto-frontier for low-dimensional task (A. 1.1), and only 3-7% of model evaluations return Pareto-optimal points (see FIG. 2A). For high-dimensional tasks computational efficiency is significantly worse, and the number of model evaluations per Pareto-optimal point grows exponentially (see FIG. 3).
2. Multi-objective Genetic Algorithms combine the use of random numbers and information from previous iterations to evaluate and improve a population of points rather than a single point at a time. GAs are based on heuristic strategies not related to the nature of multi-objective optimization. As a result, GAs are:
a. Computationally extremely intensive and resource consuming, which follows from FIG. 2B; Genetic Algorithms NSGA2 (Non-dominated Sorting Genetic Algorithm 2) and FEMO (Fair Evolutionary Multi-objective Optimizer) spend 97-99% of model evaluations to approach the Pareto-frontier for the task (A.1.1), and only 1-3% of model evaluations return Pareto-optimal points;
b. Do not provide adequate accuracy, which follows from comparison of exact solution shown on FIG. 1A with solutions found by NSGA2 and FEMO, and shown in FIGS. 1D-1E; FIG. 2A also illustrates relatively low accuracy of the solutions;
c. Do not provide an objective measure to evaluate divergence of found solutions from true Pareto frontier;
d. GAs cannot be used for high-dimensional optimization tasks with more than 40-50 design variables;
e. The objective of GAs is to find the optimal solution to a problem. However, because GAs are heuristics, the solution found is not always guaranteed to be the optimal solution. See a sample on FIGS. 1D-1E.
Traditional gradient-based optimization methods are designed to solve single-objective optimization tasks. Absence of numerical methods designed specifically for multi-objective optimization, forced engineers to invent an artificial scalarization technique, which substitutes multi-objective optimization tasks by single-objective ones, and allows using traditional gradient-based methods.
For the same reason, engineers started utilizing heuristic GAs for multi-objective optimization. Both approaches are not designed to solve multi-objective optimization tasks and do not have appropriate mathematical foundation, and as result have the above listed disadvantages.
The main optimization concept of both traditional gradient-based methods and GAs is similar: optimization process starts from initial point(s), and approaches Pareto surface in an iterative process. The concept looks simple and obvious, but causes the most substantial problems of existent optimization algorithms:                Accuracy of solution and computational efficiency strongly depend on proper determination of initial points;        There are no efficient methods to determine “good” initial points; mostly, initial points are selected randomly, which makes optimization methods too expensive;        The concept assumes that it is impossible to avoid computationally expensive approaching to Pareto surface; as result, researchers think about how to make optimization algorithms 20-50% faster instead of thinking about a new optimization paradigm, which could improve computational efficiency by orders of magnitude.        Computational time strongly depends on required accuracy.        Computational time exponentially depends on task dimension.        Some tasks cannot be solved, for instance, tasks with multiple local extremums.        
Multidisciplinary Design Optimization (MDO) is one of the most practically important fields of optimization technology because it is widely used in aerospace, automotive, turbo-machinery industries, ship design. MDO can be defined as a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines.
Very often MDO is applied to computationally expensive models that need to be optimized. For instance, Ford Motor Company reports that one crash simulation on a full passenger car takes 36-160 hours [9]. The high computational expense of such analyses limits, or even prohibits, the use of such codes in MDO. Consequently, approximation methods are commonly used in engineering design to minimize the computational expense of running such analyses and simulations.
The most often used in MDO approximation techniques includes Response Surface Methodology (RSM), Kriging Models, Artificial Neural Networks, Multivariate Splines, and Radial Basis Functions. All these approaches allow creating explicit approximation functions to objectives and constraints, and then using these when performing the optimization. Once approximations have been constructed they may be used as cheap function evaluators, replacing the underlying computationally expensive analysis tools [10].
RSM and other approximation techniques comprise regression surface fitting to obtain approximate responses, design of experiments to obtain minimum variances of the responses and optimizations using the approximated responses.
All the approximation methods require at least as many evaluations of objective functions as the number of design variables. Otherwise an accurate enough approximation cannot be created. For instance, a common optimization task with 1000 design variables requires 1000 or more evaluations of computationally expensive analysis models. This limits the range of application for the approximation methods to 20-30 design variables [11].
Often referred to as the “curse of dimensionality,” a constant challenge in building accurate approximation models is handling problems with large numbers of variables: the more design variables you have, the more samples you need to build an accurate approximation model [13]. A few approaches have been developed to handle problems with large numbers of variables. Screening experiments are often employed to reduce the set of factors to those that are most important to the response(s) being investigated [14]. Box and Draper proposed a method to gradually refine a response surface model to better capture the real function by “screening” out unimportant variables [15]. However, screening methods need an interaction with optimization. For instance, variables that might not be important during initial experimentation may become important in the later stages of the optimization such that the variables that were initially “screened out” need to be added back into the model [13]. The variable-complexity response surface modeling method uses analyses of varying fidelity to reduce the design space to the region of interest [16]. This simplifies creating an accurate approximation for middle size tasks, but still does not work for high-dimensional tasks.
Non-dimensional variables and stepwise regression were used to reduce the complexity and increase the accuracy of the response surface approximations [17]. Additionally, higher-order polynomials were used as response surface approximations, and a detailed error analysis, using an independent data set, is performed. This approach is also not efficient enough, being applied for creating a global approximation of the original model.
All approaches developed to handle problems with a large number of design variables were able to extend the task dimension limit from 20-30 to 40-60, but have not resolved the problem for large-scale tasks. The idea of substituting an original computationally expensive model by a global approximating model for further optimization cannot work for tasks with hundreds and thousands design variables [13].
The present invention offers new a type of gradient-based numerical analysis specifically targeted to solve multi-objective optimization tasks, and named Concurrent Gradients Analysis (CGA). Two multi-objective optimization methods have been invented based on CGA: Concurrent Gradients Method (CGM) and Pareto Navigator Method (PNM). CGM starts from an initial point and approaches the Pareto frontier. PNM moves along the Pareto frontier instead of approaching it on each step. This idea introduces a new concept of optimization, and allows improving computational efficiency 10-500 times. CGM and PNM are the fastest and the most accurate multi-objective optimization algorithms. The invention offers also Dimensionally Independent Response Surface Method (DIRSM). These invented methods are intended to overcome disadvantages of existent approaches.                1. Andersson J., “A Survey of Multi-objective Optimization in Engineering Design,” Fluid and Mechanical Engineering Systems, Linköping University, Sweden, LiTH-IKP-R1097.        2. Marler, R. T., and Arora, J. S. (2004), “Survey of Multi-objective Optimization Methods for Engineering”, Structural and Multidisciplinary Optimization, 26, 6, 369-395.        3. Pareto, V.1906: Manuale di Economica Politica, Societa Editrice Libraria. Milan; translated into English by A. S. Schwier as Manual of Political Economy. Edited by A. S. Schwier and A. N. Page, 1971. New York: A. M. Kelley.        4. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press: Ann Arbor, Mich.        5. Vanderplaats, G. N., Numerical Optimization Techniques for Engineering Design, McGraw-Hill Book Co., 1984.        6. Haftka, R. T., and Gurdal, Z., Elements of Structural Optimization, Kluwer Academic Publishers, 1992.        7. Walsh, G. R., Methods of Optimization, John Wiley, 1975.        8. Weiyu Liu, Development of Gradient-Enhanced Kriging Approximations for Multidisciplinary Design Optimization, Dissertation, University of Notre Dame, 2003.        9. Gu, L., “A Comparison of Polynomial Based Regression Models in Vehicle Safety Analysis,” ASME Design Engineering Technical Conferences—Design Automation Conference (DAC) (Diaz, A., ed.), Pittsburgh, Pa., ASME, Sep. 9-12, 2001, Paper No. DETC2001/DAC-21063.        10. Simpson, T. W., Peplinski, J., Koch, P. N. and Allen, J. K., “Metamodels for Computer-Based Engineering Design: Survey and Recommendations,” Engineering with Computers, Vol.17, No. 2, 2001, pp.129-150.        11. Balabanov, V., Venter G., Multi-Fidelity Optimization with High-Fidelity Analysis and Low-Fidelity Gradients, 10th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, Albany, N.Y., Aug. 30-1, 2004.        12. M. C. Fu, “Optimization for Simulation: Theory vs. Practice”, INFORMS Journal on Computing, 2002.        13. Simpson, T. W., Booker, A. J., Ghosh, D., Giunta, A. A., Koch, P. N., and Yang, R.-J. (2004) Approximation Methods in Multidisciplinary Analysis and Optimization: A Panel Discussion, Structural and Multidisciplinary Optimization, 27:5 (302-313).        14. Welch, W. J., Buck, R. J., Sacks, J., Wynn, H. P., Mitchell, T. J. and Morris, M. D., “Screening, Predicting, and Computer Experiments,” Technometrics, Vol. 34, No. 1,1992, pp.15-25.        15. Box, G. E. P. and Draper, N. R., Evolutionary Operation: A Statistical Method for Process Management, John Wiley & Sons, Inc., New York, 1969.        16. Balabanov, V. O., Giunta, A. A., Golovidov, O., Grossman, B., Mason, W. H. and Watson, L. T., “Reasonable Design Space Approach to Response Surface Approximation,” Journal of Aircraft, Vol. 36, No.1, 1999, pp. 308-315.        17. Venter, G., Haftka, R, Starnes, J., Construction of response surface approximations for design optimization. AIAA Journal, 36:2242-2249,1998. P. Vincent and Y. Bengio.        